An arithmetic processing unit such as a central processing unit (CPU) has a cache memory that is accessible at a higher speed compared with the main memory. The cache memory is disposed between a processor core such as a CPU core which is an arithmetic processor and the main memory, and stores part of the data stored in the main memory.
When the cache memory stores data specified in an access request from the processor core (cache hit), the cache memory transfers the stored data to the processor core. Also, when the data specified in the access request is not stored in the cache memory (cache miss), the cache memory obtains the data from the main memory, transfers the obtained data to the processor core, and stores the data obtained from the main memory. Thus, the data specified in the access request is registered in the cache memory.
It is to be noted that when no free space is available for registering the data obtained from the main memory, one of the pieces of data stored in the cache memory is evicted to generate free space. The least recently used (LRU) algorithm is known as a technique that selects data to be evicted from the cache memory. According to the LRU algorithm, the cache memory selects data to be evicted, which has not been used for the longest time.
It is to be noted that for a system in which the access time to the main memory varies with the storage destination of data in the main memory, a technique has been proposed that selects data to be evicted from the cache memory by a selection algorithm different from the LRU algorithm (for instance, see Japanese Laid-open Patent Publication Nos. 10-187540, 7-152649). According to this type of selection algorithm, a piece of data with the shortest access time to the main memory is preferentially selected from the data stored in the cache memory as the data to be evicted from the cache memory.